package com.tql.ArrayTest;

import java.util.*;

//斐波那契数列
public class Test {
    public static void main(String[] args) {

    }
    //斐波那契数列 1 1 2 3 5 8 13
    public static int test1(int n){
        //结束条件
        if(n==1 || n==2){
            return 1;
        }
        //递归条件
        //后一位+后后一位
        return test1(n-1)+test1(n-2);
    }
    private static Map<Integer,Integer> map=new HashMap<Integer,Integer>();
    //拍楼梯解法1，效率低
    public static int test2(int n){
       if(n==1)return 1;
       if(n==2) return 2;
       if(null!=map.get(n)){
           return map.get(n);
       }else{
           int result=test2(n-1)+test2(n-2);
           map.put(n,result);
           return result;
       }

    }
    //两数之和  1 4 8 9 10 30
    //解法1 O(n^2)
    public static int[] test3(int []arr,int target){
        int []result=new int[2];
        for (int i = 0; i < arr.length; i++) {
            for (int j=i+1;j<arr.length;j++){
                int res=arr[i]+arr[j];
                if(res==target){
                    result[0]=i;
                    result[1]=j;
                    return result;
                }
            }
        }
        return result;
    }
    //两数之和  1 4 8 9 10 30
    //解法2 采用hashmap存储 O(n)
    private static Map<Integer,Integer> params=new HashMap<Integer, Integer>();
    public static int[] test4(int []nums,int target){
        int []result=new int[2];
        for (int i = 0; i < nums.length; i++) {
            int sub=target-nums[i];
            Integer integer = params.get(sub);
            if(null!=integer){
                result[0]=i;
                result[1]=integer;
            }else{
                params.put(nums[i],i);
            }

        }
        return result;
    }
    //两数之和  1 4 8 9 10 30
    //解法3 采用hashmap存储 O(n)
    public static int[] test5(int []nums,int target){
        int []result=new int[2];
        for (int i = 0; i < nums.length; i++) {
            Integer integer = params.get(nums[i]);
            if(null!=integer){
                result[0]=i;
                result[1]=integer;
            }else{
                int sub=target-nums[i];
                params.put(sub,i);
            }

        }
        return result;
    }
    //合并俩个有序数组
    //解法1
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i < n; i++) {
            nums1[m++]=nums2[i];
        }
        Arrays.sort(nums1);
    }
    //合并俩个有序数组
    //解法2 ，通过双向指针
    public static void merge1(int[] nums1, int m, int[] nums2, int n) {
       int k=m+n;
       int []temp=new int[k];
       for (int i=0,pre=0,sux=0;i<k;i++){
           if(pre>=m) {
               temp[i] = nums2[sux++];
           }else if(sux>=n){
               temp[i]=nums1[pre++];
           }else if(nums1[pre]>nums2[sux]){
               temp[i]=nums2[sux++];
           }else{
               temp[i]=nums1[pre++];
           }
       }
        for (int i = 0; i < k; i++) {
            nums1[i]=temp[i];
        }
    }
    public static void moveZeroes(int[] nums) {
        if(nums==null){
            return;
        }
        int right=0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]!=0){
                nums[right]=nums[i];
                right++;
            }
        }
        for(int i=right;i<nums.length;i++){
            nums[i]=0;
        }
    }
    //找到消失的数字
    public static List<Integer> findDisappearedNumbers(int[] nums) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        HashMap<Integer, Integer> params = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            params.put(nums[i],1);
        }
        for (int i = 0; i < nums.length; i++) {
            Integer integer = params.get(nums[i]);
            if(integer==null){
                list.add(nums[i]);
            }
        }
        return list;
    }
    //找到消失的数字
    public static List<Integer> findDisappearedNumbers1(int[] nums) {
        int n=nums.length;
        for (int i:nums) {
            int x=(i-1)%n;
            nums[x] +=n;
        }
        List<Integer> result = new ArrayList<Integer>();
        for (int i = 0; i <n; i++) {
            if(nums[i]<=n){
                result.add(i+1);
            }
        }
        return result;
    }


}
